
'''
142. 环形链表 II
'''
from typing import Optional

from com.siyuan.ListNode import ListNode


class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 1.判断是否环形
        fast = head
        slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                break

        # 2.不是环形退出
        if not fast or not fast.next:
            return None

        # 3.找到入口
        slow = head
        while fast != slow:
            fast = fast.next
            slow = slow.next

        return slow